﻿//对称二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//bool Judge(struct TreeNode* root1, struct TreeNode* root2) {
//    if (!root1 && !root2) {
//        return true;
//    }
//    if ((!root1 && root2) || (root1 && !root2)) {
//        return false;
//    }
//    if (root1->val != root2->val) {
//        return false;
//    }
//    return Judge(root1->left, root2->right) && Judge(root1->right, root2->left);
//}
//bool isSymmetric(struct TreeNode* root) {
//    if (!root) {
//        return false;
//    }
//    return Judge(root->left, root->right);
//}

//另一棵树的子树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//bool isSameTree(struct TreeNode* root1, struct TreeNode* root2) {
//    if (!root1 && !root2) {
//        return true;
//    }
//    if ((root1 && !root2) || (!root1 && root2)) {
//        return false;
//    }
//    if (root1->val != root2->val) {
//        return false;
//    }
//    return isSameTree(root1->left, root2->left) && isSameTree(root1->right, root2->right);
//}
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
//    if (!root && !subRoot) {
//        return true;
//    }
//    if (root && !subRoot) {
//        return true;
//    }
//    if (!root && subRoot) {
//        return false;
//    }
//    //如果当根结点的数值相等时，root就不会继续往下面递归遍历了，这时会出问题
//    //例如:root中[1,1],subRoot中[1]，运行时输出false,但实际上是true
//    /*if (root->val == subRoot->val) {
//        return isSameTree(root, subRoot);
//    }*/
//    if (root->val == subRoot->val) {
//        if (isSameTree(root, subRoot)) {
//            return true;
//        }
//    }
//    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}

//void ShellSort(int* a, int n) {
//	int grep = n;
//	while (grep > 1) {
//		grep /= 2;
//		for (int k = 0; k < grep; k++) {
//			for (int i = k; i < n; i += grep) {
//				if (i + grep < n) {
//					int end = a[i + grep];
//					int j = i;
//					while (j >= 0 && a[j] > end) {
//						a[j + grep] = a[j];
//						j -= grep;
//					}
//					a[j + grep] = end;
//				}
//			}
//		}
//	}
//}